A significant job of a file system, operating system or other storage manager is to place data on storage media. Where the data is written, and when and how it is accessed, can have a significant effect on performance. A traditional file system, e.g., POSIX file system, uses logical block numbering (LBN) addressing to access data. However, as storage densities are increasing faster than the access time, for a given data set size the time needed to access the data is increasing, and thus reducing accessibility.
One alternative is to build a file system or other storage system with an index to track each data element based on the content of the data itself. The index comprises a collection of records, wherein each record may consist of a cryptographic hash (signature) of the data element, a reference count, and a pointer to where the data element is located on disk. Typically, each data element is 4, 8, 16 or 256 KB in size, and thus there may be billions of records in the index. For commercial systems having billions of records the index may be from 64 to 256 gigabytes in size. In a storage system of this nature, operations on the index can be significant, and can often be the limiting factor in the system's performance.
Thus, there is an ongoing need for storage systems not limited by the density and/or access limitations of the prior art systems.